\newcommand{\bexpandedG}[1]{\widetilde{G}[#1]}

\subsection{An $O(\min\{n\sqrt{k\log n}, nk\})$-round broadcast schedule}
\label{sec:upper}
\iflong We extend the notion of the evolution graph to the broadcast
model.  The primary difference is the addition of a new level of nodes
and edges for every round that enforces the broadcast constraint.

\smallskip
\noindent
{\em Evolution graph}: Let $V$ be the set of nodes. Consider a dynamic
network of $l$ rounds numbered $1$ through $l$ and let $G_i$ be the
communication graph for round $i$. The evolution graph for this
network is a directed capacitated graph $\bexpandedG{2l+1}$ with
$2l+1$ levels constructed as follows. We create $2l+1$ copies of $V$
and call them $V_0, V_1, V_2, \dots, V_{2l}$. $V_i$ is the set of
nodes at level $i$ and for each node $v$ in $V$, we call its copy in
$V_i$ as $v_i$. For $i = 1, \ldots, l$, level $2i-1$ corresponds to
the beginning of round $i$ and level $2i$ corresponds to the end of
round $i$. Level $0$ corresponds to the network at the start. Note
that the end of a particular round and the start of the next round are
represented by different levels. There are three kinds of edges in the
graph. First, for every round $i$ and every edge $(u,v) \in G_i$, we
place two directed edges with unit capacity each, one from $u_{2i-1}$
to $v_{2i}$ and another from $v_{2i-1}$ to $u_{2i}$. We call these
edges {\em broadcast edges} as they will correspond to broadcasting of
tokens; the unit capacity on each such edge will ensure that only one
token can be sent from a node to a neighbor in one round. Second, for
every node $v$ in $V$ and every round $i$, we place an edge with
infinite capacity from $v_{2(i-1)}$ to $v_{2i}$. We call these edges
{\em buffer edges} as they ensure tokens can be stored at a node from
the end of one round to the end of the next. Finally, for every node
$v \in V$ and every round $i$, we also place an edge with unit
capacity from $v_{2(i-1)}$ to $v_{2i-1}$. We call these edges as {\em
  selection edges} as they correspond to every node selecting a token
out of those it has to broadcast in round $i$; the unit capacity
ensures that in a given round a node must send the same token to all
its neighbors. Figure \ref{fig:evolution_broadcast} illustrates our
construction, and Lemma~\ref{lem:level.steiner} explains its
usefulness.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{level_broadcast.jpg}
\caption{An example of how to construct the evolution graph, for
  broadcast schedules, from a sequence of communication graphs.}
\label{fig:evolution_broadcast}
\end{center}
\end{figure}

\begin{lemma}
\label{lem:level.steiner}
Let there be $k$ tokens, each with a source and a set of
destinations. It is feasible to send all the tokens to all of their
destinations using $l$ rounds, where every node broadcasts only one
token in each round, iff $k$ directed Steiner trees can be packed in
$\bexpandedG{2l + 1}$ levels, one for each token with its root being
the copy of the source at level $0$ and its terminals being the copies
of the destinations at level $2l$.
\end{lemma}
\begin{proof}
Assume that $k$ tokens can be sent to all of their destinations in $l$
rounds and fix one broadcast schedule that achieves this. We will
construct $k$ directed Steiner trees as required by the lemma based on
how the tokens reach their destinations and then argue that they all
can be packed in $\bexpandedG{2l+1}$ respecting the edge
capacities. For a token $i$, we construct a Steiner tree $T^i$ as
follows.  For each level $j \in \{0, \ldots, 2l\}$, we define a set
$S^i_j$ of nodes at level $j$ inductively starting from level $2l$
backwards.  $S^i_{2l}$ is simply the copies of the destination nodes
for token $i$ at level $2l$. Once $S^i_{2(j+1)}$ is defined, we define
$S^i_{2j}$ (respectively $S^i_{2j+1}$) as: for each $v_{2(j+1)} \in
S^i_{2(j+1)}$, include $v_{2j}$ (respectively nothing) if token $i$
has reached node $v$ by round $j$, or include a node $u_{2j}$
(respectively $u_{2j+1}$) such that $u$ has token $i$ at the end of
round $j$ which it broadcasts in round $j+1$ and $(u,v)$ is an edge of
$G_{j+1}$. Such a node $u$ can always be found because whenever
$v_{2j}$ is included in $S^i_{2j}$, node $v$ has token $i$ by the end
of round $j$ which can be proved by backward induction staring from $j
= l$. It is easy to see that $S^i_0$ simply consists of the copy of
the source node of token $i$ at level $0$. $T^i$ is constructed on the
nodes in $\cup_{j = 0}^{j = 2l} S^i_j$. If for a vertex $v$,
$v_{2(j+1)} \in S^i_{2(j+1)}$ and $v_{2j} \in S^i_{2j}$, we add the
buffer edge $(v_{2j},v_{2(j+1)})$ in $T^i$. Otherwise, if $v_{2(j+1)}
\in S^i_{2(j+1)}$ but $v_{2j} \notin S^i_{2j}$, we add the selection
edge $(u_{2j},u_{2j+1})$ and broadcast edge $(u_{2j+1},v_{2(j+1)})$ in
$T^i$, where $u$ was the node chosen as described above. It is
straightforward to see that these edges form a directed Steiner tree
for token $i$ as required by the lemma which can be packed in
$\bexpandedG{2l+1}$. The argument is completed by noting that any unit
capacity edge cannot be included in two different Steiner trees as we
started with a broadcast schedule where each node broadcasts a single
token to all its neighbors in one round, and thus all the $k$ Steiner
trees can be simultaneously packed in $\bexpandedG{2l+1}$ respecting
the edge capacities.

Next assume that $k$ Steiner trees as in the lemma can be packed in
$\bexpandedG{2l+1}$ respecting the edge capacities. We construct a
broadcast schedule for each token from its Steiner tree in the natural
way: whenever the Steiner tree $T_i$ corresponding to token $i$ uses a
broadcast edge $(u_{2j-1},v_{2j})$ for some $j$, we let the node $u$
broadcast token $i$ in round $j$. We need to show that this is a
feasible broadcast schedule. First we observe that two different
Steiner trees cannot use two broadcast edges starting from the same
node because every selection edge has unit capacity, thus there are no
conflicts in the schedule and each node is asked to broadcast at most
one token in each round. Next we claim by induction that if node
$v_{2j}$ is in $T^i$, then node $v$ has token $i$ by the end of round
$j$. For $j = 0$, it is trivial since only the copy of the source node
for token $i$ can be included in $T^i$ from level $0$. For $j > 0$, if
$v_{2j}$ is in $T^i$, we must reach there by following the buffer edge
$(v_{2(j-1)},v_{2j})$ or a broadcast edge $(u_{2j-1},v_{2j})$. In the
former case, by induction node $v$ has token $i$ after round $j-1$
itself. In the latter case, node $u$ which had token $i$ after round
$j-1$ by induction was the neighbor of node $v$ in $G_j$ and $u$
broadcast token $i$ in round $j$, thus implying node $v$ has token $i$
after round $j$. From the above claim, we conclude that whenever a
node is asked to broadcast a token in round $j$, it has the token by
the end of round $j-1$. Thus the schedule we constructed is a feasible
broadcast schedule. Since the copies of all the destination nodes of a
token at level $2l$ are the terminals of its Steiner tree, we conclude
all the tokens reach all of their destination nodes after round $l$.
\end{proof}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{steiner.jpg}
\caption{An example of building directed Steiner tree in the evolution
  graph based on token dissemination process. Token $t$ starts
  from node $B$. Thus, the Steiner tree is rooted at $B_0$ in
  $G$. Since $B_0$ has token $t$, we include the infinite capacity
  buffer edge $(B_0,B_2)$. In the first round, node $B$ broadcasts
  token $t$, and hence we include the selection edge
  $(B_0,B_1)$. Nodes $A$ and $C$ receive token $t$ from $B$ in the
  first round, so we include edges $(B_1,A_2)$, $(B_1,C_2)$. Now
  $A_2$, $B_2$, and $C_2$ all have token $t$. Therefore we include the
  edges $(A_2,A_4)$, $(B_2,B_4)$, and $(C_2,C_4)$. In the second
  round, all of $A$, $B$, and $C$ broadcast token $t$, we include
  edges $(A_2,A_3)$, $(B_2,B_3)$, $(C_2,C_3)$. Nodes $D$ and $E$
  receive token $t$ from $C$. So we include edges $(C_3,D_4)$ and
  $(C_3,E_4)$. Notice that nodes $A$ and $B$ also receive token $t$
  from $C$, but they already have token $t$. Thus, we don't include
  edges $(C_3,B_4)$ or $(C_3,A_4)$.}
\label{fig:steiner}
\end{center}
\end{figure}

Our algorithm is given in Algorithm~\ref{alg:broadcast_flow_based} and
analyzed in Lemma~\ref{lem:level.flow} and
Theorem~\ref{thm:offline_broadcast}.

\begin{algorithm}[ht!]
\caption{$O(\min\{n \sqrt{k\log n}, nk\})$ round algorithm in the
  offline model}
\label{alg:broadcast_flow_based}
\begin{algorithmic}[1]
  \REQUIRE A sequence of communication graphs $G_i$, $i = 1, 2, \ldots$
  \ENSURE Schedule to disseminate $k$ tokens.

  \medskip

  \IF{$k \leq \sqrt{\log n}$}

  \FOR{each token $t$} \label{alg.step:flow_based.trivial}

  \STATE For the next $n$ rounds, let every node that has token
  $t$ broadcast the token.

  \ENDFOR 

  \ELSE

  \STATE Choose a set $S$ of $2\sqrt{k \log n}$ random nodes. \label{alg.step:random}
  
  \FOR{each vertex in $v \in S$} \label{alg.step:flow_based.phase_1}

  \STATE Send each of the $k$ tokens to vertex $v$ in $O(n)$ rounds. 

  \ENDFOR

  \FOR{each token $t$} \label{alg.step:flow_based.phase_2}

  \STATE For the next $2n \sqrt{(\log n)/k}$ rounds, let every node with token
  $t$ broadcast it.

  \ENDFOR

  \ENDIF

\end{algorithmic}
\end{algorithm}

%\vspace{-1cm}
\begin{lemma}
\label{lem:level.flow.broadcast}
Let $k \leq n$ tokens be at given source nodes and $v$ be an arbitrary
node. Then, all the tokens can be gathered at $v$ in the broadcast
model in at most $n+k$ rounds.
\end{lemma}

The proof is analogous to that for the multiport model and is omitted.

\junk{
\begin{theorem}
\label{thm:flow_based}
Algorithm~\ref{alg:flow_based} solves the $k$-gossip problem using
$O(\min\{n \sqrt{k \log n}, nk\})$ rounds with high probability in
the offline model.
\end{theorem}
}

\tOfflineBroadcast
\begin{proof}
It is trivial to see that if $k \leq \sqrt{\log n}$, then the
algorithm will end in $nk$ rounds and each node receives all the $k$
tokens. Assume $k > \sqrt{\log n}$. By Lemma~\ref{lem:level.flow}, all
the tokens can be sent to all the nodes in $S$ using $O(n \sqrt{k \log
  n})$ rounds. Now fix a node $v$ and a token $t$. Since token $t$ is
broadcast for $2n \sqrt{(\log n)/k}$ rounds, there is a set $S^t_v$ of
at least $2n \sqrt{(\log n)/k}$ nodes from which $v$ is reachable
within those rounds.  It is clear that if $S$ intersects $S^t_v$, $v$
will receive token $t$. Since the set $S$ was picked uniformly at
random, the probability that $S$ does not intersect $S^t_v$ is at most
\[ \frac{{n - 2n\sqrt{(\log n)/k} \choose 2\sqrt{k \log n}}}{{n \choose 2\sqrt{k \log n}}} < \left(\frac{n - 2n\sqrt{(\log n)/k}}{n}\right)^{2\sqrt{k \log n}} 
\le \frac{1}{n^4}.\]  
Thus every node receives every token with probability $1-1/n^3$. It is
also clear that the algorithm finishes in $O(n \sqrt{k \log n})$
rounds.
\end{proof}

Algorithm~\ref{alg:flow_based} can be derandomized using the technique
of conditional expectations, as shown in
Algorithm~\ref{alg:derandomize} and analyzed in
Lemma~\ref{lem:derandomize}.

Algorithm~\ref{alg:flow_based} can be derandomized using the standard
technique of conditional expectations, as shown in
Algorithm~\ref{alg:derandomize}.  Given a sequence of communication
graphs, if node $u$ broadcasts token $t$ for $\Delta$ rounds and every
node that receives token $t$ also broadcasts $t$ during that period,
then we say node $v$ is within $\Delta$ {\em broadcast distance} to
$u$ if and only if $v$ receives token $t$ by the end of round
$\Delta$. Let $S$ be a set of nodes, and $|S|\le 2 \sqrt{k \log
  n}$. We use $\dprob{u}{S}{T}$ to denote the probability that the
broadcast distance from node $u$ to set $X$ is greater than $2n
\sqrt{(\log n)/k}$, where $X$ is the union of $S$ and a set of
$2\sqrt{k\log n} - |S|$ nodes picked uniformly at random from $V
\setminus T$, and $\dsumprob{S}{T}$ denotes the sum, over all $u$ in
$V$, of $\dprob{u}{S}{T}$.

\begin{algorithm}[ht!]
\caption{Derandomized algorithm for Step~\ref{alg.step:random} in
  Algorithm~\ref{alg:flow_based}}
\label{alg:derandomize}
\begin{algorithmic}[1]
  \REQUIRE A sequence of communication graphs $G_i$, $i = 1, 2,
  \ldots$, and $k \ge \sqrt{\log n}$

  \ENSURE A set of $2\sqrt{k\log n}$ nodes $S$ such that the broadcast
  distance from every node $u$ to $S$ is within $2 n\sqrt{(\log
    n)/k}$.
  \medskip

  \STATE Set $S$ and $T$ be $\emptyset$.

  \FOR{each $v\in V$}

  \STATE $T = T \cup \{v\}$
  
  \IF{$\dsumprob{S \cup \{v\}}{T} \le \dsumprob{S}{T}$ \label{alg.step:cal}}

  \STATE $S = S\cup \{v\}$

%  \STATE Calculate $p=\dprob{V}{S \cup \{v\}}$. 
  
%  \IF{$p \ge 1- \frac{1}{n^3}$}

  \ENDIF

  \ENDFOR

  \STATE Return $S$

\end{algorithmic}
\end{algorithm}

\begin{lemma}
\label{lem:derandomize}
The set $S$ returned by Algorithm~\ref{alg:derandomize} contains at
most $2\sqrt{k\log n}$ nodes, and the broadcast distance from every
node to $S$ is at most $2n\sqrt{(\log n)/k}$.
\end{lemma}
\begin{proof}
Let us view the process of randomly selecting $2\sqrt{k\log n}$ nodes
as a computation tree. This tree is a complete binary tree of height
$n$. There are $n+1$ nodes on any root-leaf path. The level of a node
is its distance from the root. The computation starts from the
root. Each node at the $i$th level is labeled by $b_i \in \{0,1\}$,
where 0 means not including node $i$ in the final set and 1 means
including node $i$ in the set. Thus, each root-leaf path, $b_1b_2\dots
b_n$, corresponds to a selection of nodes.  For a node $a$ in the
tree, let $S_a$ (resp., $T_a$) denote the sets of nodes that are
included (resp., lie) in the path from root to $a$.

By Theorem~\ref{thm:offline_broadcast}, we know that for the root node $r$,
we have $\dsumprob{\emptyset}{S_r} =\dsumprob{\emptyset}{\emptyset}\le
1/n^3$.  If $c$ and $d$ are the children of $a$, then $T_c$ = $T_d$,
and there exists a real $0 \le p \le 1$ such that for each $u$ in $V$,
$\dprob{u}{S_a}{T_a}$ equals $p \dprob{u}{S_c}{T_c} +
(1-p)\dprob{u}{S_d}{T_d}$.  Therefore, $\dsumprob{S_a}{T_a}$ equals $p
\dsumprob{S_c}{T_c} + (1-p) \dsumprob{S_d}{T_d}$.  We thus obtain that
$\min\{\dsumprob{S_c}{T_c},\dsumprob{S_d}{T_d}\} \le
\dsumprob{S_a}{T_a}$.  Since we set $S$ to be $X$ in $\{S_c, S_d\}$
that minimizes $\dsumprob{X}{T_c}$, we maintain the invariant that
$\dsumprob{S}{T} \le 1/n^3$.  In particular, when the algorithm
reaches a leaf $l$, we know $\dsumprob{S_l}{V}\le 1/n^3$.  But a leaf
$l$ corresponds to a complete node selection, so that
$\dprob{u}{S_l}{V}$ is 0 or 1 for all $u$, and hence
$\dsumprob{S_l}{V}$ is an integer.  We thus have $\dsumprob{S_l}{V} =
0$, implying that the broadcast distance from node $u$ to set $S_l$ is
at most $2n \sqrt{(\log n)/k}$ for every $l$.  Furthermore, $|S_l|$ is
$2 k \sqrt{\log n}$ by construction.

Finally, note that Step~\ref{alg.step:cal} of
Algorithm~\ref{alg:derandomize} can be implemented in polynomial time,
since for each $u$ in $V$, $\dprob{u}{S}{T}$ is simply the ratio of
two binomial coefficients with a polynomial number of bits.  Thus,
Algorithm~\ref{alg:derandomize} is a polynomial time algorithm with
the desired property.
\end{proof}
\else
We extend the notion of the evolution graph to the broadcast model and
show that finding a broadcast schedule for $k$-gossip can be reduced
to packing Steiner trees in the evolution graph.  We defer this
section to the full paper.
\fi
